package merge

import (
	"slices"
	"sort"
)

/*
前述几种排序算法都属于“基于比较的排序算法”，它们通过比较元素间的大小来实现排序。此类排序算法的
时间复杂度无法超越𝑂(𝑛log𝑛)。接下来，我们将探讨几种“非比较排序算法”，它们的时间复杂度可以达
到线性阶。
桶排序（bucketsort）是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数
据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合
并
*/
/* 桶排序 */
func bucketSort(nums []int) {
	// 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
	numSince := slices.Max(nums) - slices.Min(nums)
	k := len(nums) / 2
	buckets := make([][]int, k)
	//創建桶 並初始化
	for i := 0; i < k; i++ {
		buckets[i] = make([]int, 0)
	}
	//1.将数组元素分配到各个桶中
	for _, num := range nums {
		//输入数据范围为[0, 1)，使用num * k映射到索引范围[0,k-1]
		// 0 ~ k
		// minNum ~ maxNum
		// 0 	~ 	num
		i := (k - 1) * num / numSince
		//将num添加进桶i
		buckets[i] = append(buckets[i], num)
	}
	//2.对各个桶执行排序
	for i := 0; i < k; i++ {
		//使用内置切片排序函数，也可以替换成其他排序算法
		if len(buckets[i]) == 0 {
			continue
		}
		slices.Sort(buckets[i])
	}
	//3.遍历桶合并结果
	i := 0
	for _, bucket := range buckets {
		if len(bucket) == 0 {
			continue
		}
		for _, num := range bucket {
			nums[i] = num
			i++
		}
	}
}

/* 桶排序 */
func bucketSortFloat(nums []float64) {
	// 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
	k := len(nums) / 2
	buckets := make([][]float64, k)
	for i := 0; i < k; i++ {
		buckets[i] = make([]float64, 0)
	}
	//1.将数组元素分配到各个桶中
	for _, num := range nums {
		//输入数据范围为[0, 1)，使用num* k映射到索引范围[0,k-1]
		i := int(num * float64(k))
		//将num添加进桶i
		buckets[i] = append(buckets[i], num)
	}
	//2.对各个桶执行排序
	for i := 0; i < k; i++ {
		//使用内置切片排序函数，也可以替换成其他排序算法

		sort.Float64s(buckets[i])
	}
	//3.遍历桶合并结果
	i := 0
	for _, bucket := range buckets {
		for _, num := range bucket {
			nums[i] = num
			i++
		}
	}
}
